package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-07-06 17:34
 */
public class 题库_0198_打家劫舍 {

  static
  class Solution {
    public int rob(int[] nums) {
      if (nums == null || nums.length == 0) {
        return 0;
      }
      if (nums.length == 1) {
        return nums[0];
      }
      return dp(nums);
//      return backtrack(0, nums, 0);
    }

    private int dp(int[] nums) {
      int preMax = nums[0];
      int pre = nums[1];
      int answer = Math.max(preMax, pre);

      for (int i = 2; i < nums.length; ++i) {
        int cur = Math.max(pre, preMax + nums[i]);
        preMax = Math.max(preMax, pre);
        pre = cur;
        answer = Math.max(answer, cur);
      }

      return answer;
    }

    private int backtrack(int index, int[] nums, int answer) {
      if (index >= nums.length) {
        return answer;
      }

      // 取当前房间 和 不取当前房间 大的一个
      return Math.max(backtrack(index + 2, nums, answer + nums[index]), backtrack(index + 1, nums, answer));
    }
  }

}
